#include<iostream>
#include<cstring>

using namespace std;

const int F=1111;

int a[F][F];

inline int min(int cyh,int mango){return cyh<mango?cyh:mango;}

int main()
{
	memset(a,63,sizeof(a));
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=min(a[x][y],z);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				a[j][k]=min(a[j][k],a[j][i]+a[i][k]);
	int ans=0;
	for(int i=2;i<=n;i++)
		ans+=a[i][1]+a[1][i];
	cout<<ans;
	return 0;
}